perm filename WINGED[00,BGB]2 blob
sn#111639 filedate 1974-07-17 generic text, type T, neo UTF8
{F1;F2;F3;[C;<N;αWINGED EDGE.;λ30;P16;I425,0;JC;FA} SECTION 2.
{JC;FD} THE WINGED EDGE POLYHEDRON REPRESENTATION.
{λ10;W250;JA;FA}
2.0 Introduction to the Winged Edge.
2.1 Winged Edge Link Fields.
2.2 Perimeter Accessing.
2.3 Lowest Level Polyhedron Synthesis and Alteration.
2.4 Edge and Face Splitting.
2.5 Coordinate Free Polyhedron Representation.
{λ30;W0;I950,0;JU}
[2.0 Introduction to the Winged Edge.]
In this chapter, a particular computer representation for
polyhedra is presented and some of its virtues and faults are explained. The
representation is implemented as a data structure composed of small
blocks of words containing pointers and data in the fashion usual to
graphics and simulation. An introduction to such data structures can be
found in Knuth (Art of Computer Programming, chapter 2, volume I).
Quickly reviewing Knuth's terminology: a node is a group of
consecutive words of memory, a field is a named portion of a node and
a link is the absolute machine address of a node. The notation for
referring to a field of a node consists simply of the field name
followed by a link expression enclosed in parentheses. For example,
the two faces of an edge node whoes link is stored in the variable named
"edge", are found in the fields named NFACE and PFACE, and are referred
to as NFACE(edge) and PFACE(edge). Although my latest language of
implementation is PDP-10 machine code, examples will be given in a
fictional programming language which combines ALGOL
with Knuthian node/link notation.{Q}
{H7;O0,630,700;
L0,-20,0*5,-61*5;L0,20,0*5,61*5;
L-86*5,83*5,0*5,61*5,86*5,83*5;L-86*5,-83*5,0*5,-61*5,86*5,-83*5;
H2;
L42*5,106*5,86*5,83*5,126*5,0*5,86*5,-83*5,42*5,-106*5,-42*5,-106*5;
L-42*5,-106*5,-86*5,-83*5,-126*5,0*5,-86*5,83*5,-42*5,106*5,42*5,106*5;
L-30,-10;FB }edge
{L-380,-10; }NFACE(edge)
{L240,-10; }PFACE(edge)
{L-70,-370; }NVT(edge)
{L-70,350; }PVT(edge)
{L-360,320; }NCCW(edge)
{L-390,-360; }NCW(edge)
{L220,320; }PCW(edge)
{L260,-360; }PCCW(edge)
{I1300,0;O0,630,950;
λ10;JC;FA} [FIGURE 2.1 - Winged Edge Topology.]
The orientation of links is as viewed from the exterior side of the surface.
The eight mnemonics in the figure, were derived as follows:
NFACE(edge) Negative Face of edge.
PFACE(edge) Positive Face of edge.
PVT(edge) Positive Vertex of edge.
NVT(edge) Negative Vertex of edge.
NCW(edge) edge in Negative face Clockwise from edge.
PCW(edge) edge in Positive face Clockwise from edge.
NCCW(edge) edge in Negative face Counter Clockwise from edge.
PCCW(edge) edge in Positive face Counter Clockwise from edge.{λ30;FA}
{Q}
[2.1 Winged Edge Link Fields.]
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. In this
context, a ring is a doubly linked circular list with a head node.
Each face and each vertex points at only one of the edges on its
perimeter. Each edge points at its two faces and its two vertices.
Completing the topology, each edge node contains a link to each of
its four immediate neighboring edges clockwise and counter clockwise
about its face perimeters as seen from the exterior side of the surface
of the polyhedron. These last four links are the wings of the edge,
which provide the basis for efficient face perimeter and vertex
perimeter accessing. Finally, the links of the edge nodes can be
consistently oriented with respect to the surface of the polyhedron
so that the surface always has two sides: the inside and the outside.
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. If we allow a link name such as PED
to serve different roles depending on whether it applies to a body,
face, edge or vertex; then the minimum number of different link field
names that need to be coined is ten. The data structures and the link
fields comprising the structures are listed in box (2.1) below. The
ten links names include: NFACE and PFACE for two fields that contain
face links in edges and the face ring, NED and PED for two fields
that contain edge links, NVT and PVT for two fields that contain
vertex links, and NCW, PCW, NCCW and PCCW for the four fields that
contain edge links and are called the wings.
{|;λ10;JA}
BOX 2.1 Data Structure Link Names
1. Face Ring of a Body. NFACE PFACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW NCCW PCCW
{|;λ30;JU}
By constraining the arrangement of links in an edge node both
the surface orientataion (interior and exterior) and a linear
orientation of the edge as a directed vector can be encoded. Figure
2.1 diagrams the arrangement of the links comprising the topology of
an edge of a polyhedron as viewed from the exterior side of its
surface. Although the vertices in figure 2.1 are shown with only
three edges, vertices may have any number of edges; the other
potential edges would not be directly linked to the middle edge of
the figure and so were not shown. To complete the representation,
space is allocated to contain the 3-D coordinates of each vertex in
fields named XWC, YWC and ZWC; the initials "WC" stand for <world
coordinates>. Further important (but not fundamental) data fields
include, the 3-D perspective projected coordinates of each vertex
with respect to a camera (one camera at a time) in fields named XPP,
YPP, ZPP of vertex nodes. Faces on the other hand carry exterior
pointing normal vectors and several words of photometric surface
characteristics. The face vectors are derived from surface topology
and vertex loci, and so are not basic geometric data as in some
representations. A specific winged edge node format of implementation
is given in appendix (**).
The Winged Edge polyhedron representation as just presented
complete. Edge nodes carry most of the topology, vertex nodes carry
the geometry, face nodes carry the photometry and body nodes carry
the semantics. The point that remains to be demonstrated, is that
the appropriate subroutines for creating, maintaining and exploiting
edge orientation are are easily coded, execute efficiently and
provide good primitives for solving such geometric problems as hidden
line elimination and polyhedral intersection.
[2.2 Perimeter Accessing.]
The perimeter of a face is an ordered list of edges and vertices,
the perimeter of a vertex is an ordered list of edges and faces, and the
perimeter of an edge is an ordered list consisting of exactly two faces
and two vertices. The perimeter definitions are caricatured in figure (2.2).
One virtue of the winged edge representation is that the perimeters can be
traveled in either direction (clockwise or counter clockwise) and are always
maintained in order.
Given one edge of a face (or vertex) perimeter, the next edge
clockwise (or counter clockwise) from the given edge about the
particular face (or vertex) can be retrieved from the data structure
with the assistance of two subroutines called ECW and ECCW. The idea
of the edge clocking routines is to match the given face (or vertex)
with one of the faces (or vertices) of the given edge and to then
return the appropriate wing. A possible coding of ECCW and ECW might
be as follows:
{↓;JA;λ7;F3}
COMMENT FETCH EDGE CCW FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
IF PFACE(E)=FV THEN RETURN(PCCW(E));
IF NFACE(E)=FV THEN RETURN(NCCW(E));
IF PVT(E)=FV THEN RETURN(PCW(E));
IF NVT(E)=FV THEN RETURN(NCW(E));
FATAL;
END "ECCW";
{↑;W670;JA;λ7;F3}
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
IF PFACE(E)=FV THEN RETURN(PCW(E));
IF NFACE(E)=FV THEN RETURN(NCW(E));
IF PVT(E)=FV THEN RETURN(NCCW(E));
IF NVT(E)=FV THEN RETURN(PCCW(E));
FATAL;
END "ECW";
{W0;JUFA;λ30;}
The first edge of a face or vertex is (of course) directly
available from the PED field of the face or vertex. For example, the
two code fragments below can be used to visit all the edges of a face or
or all the edges of a vertex, respectively.
{JA;↓;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A FACE;
BEGIN
INTEGER F,E,E0;
E←E0←PED(F);
DO FUNCTION(E) UNTIL E0=(E←ECCW(E,F));
END;
{↑;W670;JA;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A VERTEX;
BEGIN
INTEGER V,E,E0;
E←E0←PED(V);
DO FUNCTION(E) UNTIL E0=(E←ECCW(E,V));
END;
{JUFA;W0;λ30;}
Using the same idea as in the edge clocking routines, a face
or vertex can be retrieved relative to a given edge and a given face
or vertex. These routines include: FCW and FCCW which return the face
clockwise or counter clockwise from a given edge with respect to a
given vertex; VCW and VCCW which return the vetex clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which return the face or vertex of the given edge opposite the
given face or vertex. Together the seven routines: ECW, ECCW, VCW,
VCCW, FCW, FCCW and OTHER exhaust the possible oriented retrievals
from an edge node; they also alleviate the need to ever explicitly
reference a wing field when traveling the surface of a polyhedron.
With node type checking and signed arguments the seven perimeter
accessing routines could be replaced by a single routine perhaps
named PERIMETER_FETCH or PGET. On the otherhand, the proliferation of
accessing names declares the direction and node type for for
assembling better in line code. {Q}
[2.3 Edge and Face Splitting.]
Another simple virture of the winged edge representation is
that edges and faces can be split using subroutines that make only
local alterations to the data structure; likewise, the splits can be
easily removed since the doubly linked rings allow rapid deletion of
nodes from a body. The edge split routine, ESPLIT, makes a new edge
and a new vertex and places them into the surface topology as shown
in figure (2.3). The kill edge-vertex routine, KLEV, undoes an
ESPLIT. The face split routine, MKFE, creates a new edge and a new
face and places them into the surface topology as shown in figure
(2.4); the kill face-edge routine, KLFE, undoes a MKFE.
{JA;H1;I∂5,1260;V∂0,0;I∂-5,0;λ10;
JA}FIGURE 2.3{JC} ESPLIT AND KLEV.
{I∂0,200;}VNEW ← ESPLIT(E);{I∂0,800;}E ← KLEV(VNEW);
{H3;X0.5;
I∂180,315; *FIG2.3A;
I∂0,315+630; *FIG2.3B;
I∂275,0;
JA;H1;I∂5,1260;V∂0,0;I∂-5,0;λ10;
}FIGURE 2.4{JC} MKFE AND KLFE
{I∂0,200;}ENEW ← MKFE(V1,F,V2);{I∂0,800;}F ← KLFE(ENEW);
{H3;X0.5;
I∂180,315; *FIG2.4A;
I∂0,315+630; *FIG2.4B;
I∂150,0;λ30;}
{JA;W300;λ10;F3}
INTEGER PROCEDURE ESPLIT (INTEGER E);
BEGIN "ESPLIT"
INTEGER VNEW,ENEW,
COMMENT CREATE A NEW EDGE AND VERTEX ON THE BODY;
VNEW ← MKV(E);
ENEW ← MKE(E);
COMMENT CONNECT VERTICES AND FACES TO EDGES;
PVT(ENEW) ← PVT(E);
NVT(ENEW) ← VNEW;
PVT(E) ← VNEW;
PFACE(ENEW) ← PFACE(E);
NFACE(ENEW) ← NFACE(E);
COMMENT CONNECT EDGES TO VERTICES;
IF PED(V)=E THEN PED(V)←ENEW;
PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
NCW(ENEW) ← E; PCCW(ENEW) ← E;
PCW(E) ← ENEW; PCCW(E) ← ENEW;
WING(NCCW(E),ENEW);
WING(PCW(E),ENEW);
RETURN(VNEW);
END "ESPLIT";
{JU;W0;λ30;FA}
[2.4 Lowest Level Polyhedron Synthesis and Alteration.]
This section concerns the details of link manipulation which
are beneath the Euler primitives explained in the next section.
The direct handling of links is not required of the ordinary user
of winged polyhedra, but is discussed here from the view point of
implementation. Internal to a modeling system, the geometry and
topology of a desired polyhedron becomes available in some
non-standard format and a winged edge model is desired. Although bulk
conversion from an alein external polyhedron format into a winged
edge format is occassionally important, the same details apply when
altering an existing structure.
In the typical situation, there are five steps: first, get
the proper kinds of nodes into the body rings using the MKF, MKE, MKV
primitives. second, place the vertices by setting their XWC, YWC, ZWC
fields; third, connect each vertex and face pointed to one of its
edges by setting their PED fields. fourth, connect each edge to its
two faces and its two vertices by setting their NFACE, PFACE, NVT,
PVT fields. Finally, create the wing perimeter pointers by applying
the WING primitive to pairs of edges to be mated.
{|;λ10;JA}
BOX {JC} LOWEST LEVEL WINGED EDGE ROUTINES.
MKB,MKF,MKE,MKV,MKFRAME. Make body, face, edge, vertex or frame node.
WING,INVERT,EVERT Setup or change wing pointers.
LINKED Find whether two entities are linked.
ECW,ECCW Edge fetching around Face and Vertex perimeters.
OTHER,VCW,VCCW,FCW,FCCW Face/Vertex fetching from an edge.
BDET,BATT,BGET Body parts linking and body get.
{|;λ30;JU}
[2.5 Coordinate Free Polyhedron Representation.]
As in general relativity, all geometric entities can be
represented in a coordinate free form. In particular, the vertex
coordinates of a polyhedra can be recovered from edge lengths and
dihedral angles (the angle formed by the two faces at each edge).
Having the geometry carried by only two numbers per edge rather than
by three numbers per vertex does not necessarily yield a more concise
representation because edges always outnumber vertices two for one,
and in the case of a triangulated polyhedron edges outnumber vertices
by three to one.
One application of a coordinate free representation arises
when it is necessary to measure a complicated shape with simple tools
such as a caliper and straight edge. For example, one way to go about
recording the topology and geometry of an arbitrary object is to draw
a triangulated polyhedron on its surface with serial numbered
vertices and record for each edge its length, its two vertices and
its <signed dihedral length>. The dihedral length is the distance
between the vertices opposite the edge in each of the edge's two
triangles, the length can be given a sign convention to indicate
whether the edge is concave or convex. The required dihedral angles
can then be computed from the signed dihedral lengths.